树形数据的搜索方法

2024-06-20 14:04| 来源: 网络整理| 查看: 265

说明

假设有这样的问题。给一个如下数据结构的数据。然后求id=01001002的text值。

var tree = [{ id: '01000000', text: '北京', children: [{ id: '01001000', text: '北京市', children: [ { id: '01001001', text: '西城区', children: null },{ id: 12, text: '东城区', children: null } ] }] },{ id: '02000000', text: '上海', children: [{ id: '02001000', text: '上海市', children: [{ id: '02001001', text: '黄浦区', children: null }] }] }];

这是个很明显的多叉树的树形结构，一般情况下，对于这种树形结构一般采用深度优先遍历和广度优先遍历。

深度优先遍历

深度优先遍历的原则是： 1. 从顶点开始； 2. 如果当前节点有子节点，则遍历当前节点的所有子节点；

// 递归实现 function deepSearch(tree){ for(var i = 0; i0) { deepSearch(tree[i].children); } } } // 非递归 function deepSearch(tree) { var stark = []; stark = stark.concat(tree); while(stark.length) { var temp = stark.shift(); if(temp.children) { // 当前节点有子节点时，将子节点放到当前的栈的前面 stark = temp.children.concat(stark); } console.log(temp); } }

回到我们的问题，我们可以给出以下两种解法：

// 递归 function deepQuery(tree,id) { var isGet = false; var retNode = null; function deepSearch(tree,id){ for(var i = 0; i0) { deepSearch(tree[i].children,id); } if(id === tree[i].id || isGet) { isGet||(retNode = tree[i]); isGet = true; break; } } } deepSearch(tree,id); return retNode; } // 非递归 function deepQuery(tree, id){ var stark = []; stark = stark.concat(tree); while(stark.length) { var temp = stark.shift(); if(temp.children) { stark = temp.children.concat(stark); } if(id === temp.id) { return temp; } } }

递归没办法及时跳出循环，所以在外面定义一个标记为，表示有没有找到要搜索的结果，如果找到，则跳出后续的循环。非递归的直接找到结果的时候return就行。

广度优先遍历

广度优先遍历的原则是： 1. 从根节点开始； 2. 遍历所有子节点； 3. 从第一个子节点开始再执行广度优先遍历。代码如下：

针对我们的问题的解法：

当数据没有规则的时候，我们通常只能使用遍历的方式来搜索我们想要的数据。但是假设我们的数据有这样的特点： 1. id由八位数字构成； 2. 1-2位表示省； 3. 3-5位表示市； 4. 6-8位表示县； 5. 缺省用0代替，比如北京的省级的id是1，则北京这个省级区域的id 的为 01000000。则这时候给我们一个id，我们就可以快速获得他的各个层级的id了，以便于快速定位。这种方式只适合于那种层级固定的且id有一定规则的数据。

【本文地址】

树形数据的搜索方法

树形数据的搜索方法

今日新闻

推荐新闻